package bintree.leetcode;

/**
 * @Author: yuisama
 * @Date: 2022/9/28 16:47
 * @Description:二叉树转为单向链表
 */
public class Num114_Flatten {
    /**
     * 分解问题
     * 传入一颗二叉树的根节点root。就能将二叉树拉平为单链表
     * @param root
     */
    public void flatten(TreeNode root) {
        // base case
        if (root == null) return;
        // 分解问题，先拆分左右子树
        flatten(root.left);
        flatten(root.right);
        TreeNode right = root.right;
        // 将拆分好的左链表拼接到树根右侧
        root.right = root.left;
        // 这里记得要断左子树的引用!
        root.left = null;
        // 寻找当前这个链表的链表尾部
        TreeNode last = root;
        while (last.right != null) {
            last = last.right;
        }
        // 拼接原右链表
        last.right = right;
    }
}
